void dfs(int now) {
	use[now]=true;
	for (edge *e=v[now];e;e=e->next)
		if (!use[e->e]) dfs(e->e);
}

void bfs(int now) {
	int front=tail=1;
	q[1]=now;
	use[now]=true;
	for (;front<=tail;) {
		int now=q[front++];
		for (edge *e=v[now];e;e=e->next)
			if (!use[e->e]) {
				q[++tail]=e->e;
				use[e->e]=true;
			}
	}
}

void floyd() {
	memset(dist,0x3f,sizeof(dist));
	for (int a=1;a<=m;a++)
		dist[s[a]][e[a]]=min(dist[s[a]][e[a]],d[a]);
	for (int a=1;a<=n;a++)
		dist[a][a]=0;
	for (int a=1;a<=n;a++)
		for (int b=1;b<=n;b++)
			for (int c=1;c<=n;c++)
				dist[b][c]=min(dist[b][c],dist[b][a]+dist[a][c]);
}

void dijkstra(int s) {
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for (int a=1;a<=n;a++) {
		int p=-1;
		for (int b=1;b<=n;b++)//O(n^2)
			if (!use[b] && (p==-1 || dist[b]<dist[p]) p=b;
		use[p]=true;
		for (edge *e=v[p];e;e=e->next)//O(m)
			dist[e->e]=min(dist[e->e],dist[p]+e->d);
	}
}


	struct rec{
		int p,d;
		rec(){p=d=0;}
		rec(int a,int b){p=a,d=b;}
		bool operator<(const rec&a)const{
			return d>a.d;
		}
	};

void dijkstra_heap(int s) {
	priority_queue<rec> heap;
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	heap.push(rec(s,0));
	for (int a=1;a<=n;a++) {
		while (use[heap.top().p])
			heap.pop();
		int p=heap.top().p;
		use[p]=true;
		for (edge *e=v[p];e;e=e->next)
			if (dist[e->e]>dist[p]+e->d) {
				dist[e->e]=dist[p]+e->d;
				heap.push(rec(e->e,dist[e->e]);
			}
	}
}//(m+n)log(m+n)+m
//(m+n)logn+m Shouxie Heap
//nlogn+m Fib Heap

void Bellman-Ford(int now) {
	memset(dist,0x3f,sizeof(dist));
	dist[now]=0;
	for (int a=1;a<=n;a++)
		for (int b=1;b<=m;b++)
			dist[e[b]]=min(dist[e[b]],dist[s[b]]+d[b]);
}//O(nm)

int q[maxn];
void spfa(int now) {// O(km)
	memset(dist,0x3f,sizeof(dist));
	dist[now]=0;
	int front=1,tail=2;
	q[1]=now;
	use[now]=true;
	for (;front!=tail;) {
		int now=q[front++];
		if (front==maxn) front=0;
		use[now]=false;
		for (edge *e=v[now];e;e=e->next)
			if (dist[e->e]>dist[now]+e->d) {
				dist[e->e]=dist[now]+e->d;
				pre[e->e]=now;
				if (!use[e->e]) {
					q[tail++]=e->e;
					if (tail==maxn) tail=0;
					use[e->e]=true;
				}
			}
	}
}

void prim()
{
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	for (int a=1;a<=n;a++) {
		int p=-1;
		for (int b=1;b<=n;b++)//O(n^2)
			if (!use[b] && (p==-1 || dist[b]<dist[p]) p=b;
		use[p]=true;
		for (edge *e=v[p];e;e=e->next)//O(m)
			dist[e->e]=min(dist[e->e],e->d);
	}
}
